home *** CD-ROM | disk | FTP | other *** search
/ Scene Storm / Scene Storm - Volume 1.iso / coding / c / zoo / encode.c < prev    next >
C/C++ Source or Header  |  1980-01-02  |  8KB  |  335 lines
  1. /*$Source: /usr/home/dhesi/zoo/RCS/encode.c,v $*/
  2. /*$Id: encode.c,v 1.41 91/07/09 01:39:47 dhesi Exp $*/
  3.  
  4. /*
  5. Adapted from "ar" archiver written by Haruhiko Okumura.
  6. */
  7.  
  8. #include "options.h"
  9. #include "zoo.h"
  10. #include "ar.h"
  11. #include "lzh.h"
  12. #include "zooio.h"
  13. #include "zoofns.h"
  14.  
  15. extern char *out_buf_adr;
  16.  
  17. #include <assert.h>
  18.  
  19. #ifdef ANSI_HDRS
  20. # include <stdlib.h>
  21. # include <string.h>
  22. #endif
  23.  
  24. #include "errors.i"
  25.  
  26. FILE *lzh_infile;
  27. FILE *lzh_outfile;
  28.  
  29. #if 0
  30. void d1log(char *fmt, ...)
  31. {
  32.      printf(fmt, ((long *)&fmt)[1], ((long *)&fmt)[2], ((long *)&fmt)[3],
  33.       ((long *)&fmt)[4], ((long *)&fmt)[5]);
  34. }
  35. #endif
  36.  
  37. /*
  38. sliding dictionary with percolating update
  39. */
  40.  
  41. #define PERCOLATE  1
  42. #define NIL  0
  43. #define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX)
  44.  
  45. typedef short node;
  46.  
  47. static uchar *text, *childcount;
  48. static node pos, matchpos, avail,
  49.     *position, *parent, *prev, *next = NULL;
  50. static int remainder, matchlen;
  51.  
  52. #if MAXMATCH <= (UCHAR_MAX + 1)
  53.     static uchar *level;
  54. # define T_LEVEL    uchar *
  55. #else
  56.     static ushort *level;
  57. # define T_LEVEL    ushort *
  58. #endif
  59.  
  60. static void makechild PARMS((node, int /*=uchar*/, node));
  61. static node child PARMS((node, int /*=uchar*/));
  62. void split PARMS((node));
  63. static void delete_node PARMS((void));
  64. static void insert_node PARMS((void));
  65. static void allocate_memory PARMS((void));
  66. static void init_slide PARMS((void));
  67. static void get_next_match PARMS((void));
  68.  
  69. static void allocate_memory()
  70. {
  71.     if (next != NULL) return;
  72.     /* text = (uchar *) malloc(DICSIZ * 2 + MAXMATCH); */
  73.     text = (uchar *) out_buf_adr; /* reuse I/O buffer used elsewhere */
  74.     level = (T_LEVEL) malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
  75.     childcount = (uchar *)malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
  76. #ifdef PERCOLATE
  77.       position = (node *) malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*position));
  78. #else
  79.       position = (node *) malloc(DICSIZ * sizeof(*position));
  80. #endif
  81.     parent      = (node *) malloc(DICSIZ * 2 * sizeof(*parent));
  82.     prev          = (node *) malloc(DICSIZ * 2 * sizeof(*prev));
  83.     next          = (node *) malloc((MAX_HASH_VAL + 1) * sizeof(*next));
  84.     if (next == NULL) prterror('f', no_memory);
  85. }
  86.  
  87. void init_slide()
  88. {
  89.     node i;
  90.  
  91.     for (i = DICSIZ; i <= DICSIZ + UCHAR_MAX; i++) {
  92.         level[i] = 1;
  93. #ifdef PERCOLATE
  94.             position[i] = NIL;  /* sentinel */
  95. #endif
  96.     }
  97.     for (i = DICSIZ; i < DICSIZ * 2; i++) parent[i] = NIL;
  98.     avail = 1;
  99.     for (i = 1; i < DICSIZ - 1; i++) next[i] = i + 1;
  100.     next[DICSIZ - 1] = NIL;
  101.     for (i = DICSIZ * 2; i <= MAX_HASH_VAL; i++) next[i] = NIL;
  102. }
  103.  
  104. #define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2)
  105.  
  106. node child(q, c)
  107. node q;
  108. int /*=uchar*/ c;
  109.     /* q's child for character c (NIL if not found) */
  110. {
  111.     node r;
  112.  
  113.     r = next[HASH(q, c)];
  114.     parent[NIL] = q;    /* sentinel */
  115.     while (parent[r] != q) r = next[r];
  116.     return r;
  117. }
  118.  
  119. void makechild(q, c, r)
  120. node q;
  121. int /*=uchar*/ c;
  122. node r;
  123.     /* Let r be q's child for character c. */
  124. {
  125.     node h, t;
  126.  
  127.     h = HASH(q, c);
  128.     t = next[h];  next[h] = r;  next[r] = t;
  129.     prev[t] = r;  prev[r] = h;
  130.     parent[r] = q; childcount[q]++;
  131. }
  132.  
  133. void split(old)
  134. node old;
  135. {
  136.     node new, t;
  137.  
  138.     new = avail;  avail = next[new];  childcount[new] = 0;
  139.     t = prev[old]; prev[new] = t; next[t] = new;
  140.     t = next[old]; next[new] = t; prev[t] = new;
  141.     parent[new] = parent[old];
  142.     level[new] = matchlen;
  143.     position[new] = pos;
  144.     makechild(new, text[matchpos + matchlen], old);
  145.     makechild(new, text[pos + matchlen], pos);
  146. }
  147.  
  148. void insert_node()
  149. {
  150.     node q, r, j, t;
  151.     uchar c, *t1, *t2;
  152.  
  153.     if (matchlen >= 4) {
  154.         matchlen--;
  155.         r = (matchpos + 1) | DICSIZ;
  156.         while ((q = parent[r]) == NIL) r = next[r];
  157.         while (level[q] >= matchlen) {
  158.             r = q;    q = parent[q];
  159.         }
  160. #ifdef PERCOLATE
  161.             t = q;
  162.             while (position[t] < 0) {
  163.                 position[t] = pos;  t = parent[t];
  164.             }
  165.             if (t < DICSIZ) position[t] = pos | PERC_FLAG;
  166. #else
  167.             t = q;
  168.             while (t < DICSIZ) {
  169.                 position[t] = pos;  t = parent[t];
  170.             }
  171. #endif
  172.     } else {
  173.         q = text[pos] + DICSIZ;  c = text[pos + 1];
  174.         if ((r = child(q, c)) == NIL) {
  175.             makechild(q, c, pos);  matchlen = 1;
  176.             return;
  177.         }
  178.         matchlen = 2;
  179.     }
  180.     for ( ; ; ) {
  181.         if (r >= DICSIZ) {
  182.             j = MAXMATCH;    matchpos = r;
  183.         } else {
  184.             j = level[r];
  185.             matchpos = position[r] & ~PERC_FLAG;
  186.         }
  187.         if (matchpos >= pos) matchpos -= DICSIZ;
  188.         t1 = &text[pos + matchlen];  t2 = &text[matchpos + matchlen];
  189.         while (matchlen < j) {
  190.             if (*t1 != *t2) {  split(r);  return;  }
  191.             matchlen++;  t1++;  t2++;
  192.         }
  193.         if (matchlen >= MAXMATCH) break;
  194.         position[r] = pos;
  195.         q = r;
  196.         if ((r = child(q, *t1)) == NIL) {
  197.             makechild(q, *t1, pos);  return;
  198.         }
  199.         matchlen++;
  200.     }
  201.     t = prev[r];  prev[pos] = t;    next[t] = pos;
  202.     t = next[r];  next[pos] = t;    prev[t] = pos;
  203.     parent[pos] = q;    parent[r] = NIL;
  204.     next[r] = pos; /* special use of next[] */
  205. }
  206.  
  207. void delete_node()
  208. {
  209. #ifdef PERCOLATE
  210.         node q, r, s, t, u;
  211. #else
  212.         node r, s, t, u;
  213. #endif
  214.  
  215.     if (parent[pos] == NIL) return;
  216.     r = prev[pos]; s = next[pos];
  217.     next[r] = s;  prev[s] = r;
  218.     r = parent[pos];    parent[pos] = NIL;
  219.     if (r >= DICSIZ || --childcount[r] > 1) return;
  220. #ifdef PERCOLATE
  221.         t = position[r] & ~PERC_FLAG;
  222. #else
  223.         t = position[r];
  224. #endif
  225.     if (t >= pos) t -= DICSIZ;
  226. #ifdef PERCOLATE
  227.         s = t;    q = parent[r];
  228.         while ((u = position[q]) & PERC_FLAG) {
  229.             u &= ~PERC_FLAG;    if (u >= pos) u -= DICSIZ;
  230.             if (u > s) s = u;
  231.             position[q] = (s | DICSIZ);  q = parent[q];
  232.         }
  233.         if (q < DICSIZ) {
  234.             if (u >= pos) u -= DICSIZ;
  235.             if (u > s) s = u;
  236.             position[q] = s | DICSIZ | PERC_FLAG;
  237.         }
  238. #endif
  239.     s = child(r, text[t + level[r]]);
  240.     t = prev[s];  u = next[s];
  241.     next[t] = u;  prev[u] = t;
  242.     t = prev[r];  next[t] = s;  prev[s] = t;
  243.     t = next[r];  prev[t] = s;  next[s] = t;
  244.     parent[s] = parent[r];    parent[r] = NIL;
  245.     next[r] = avail;    avail = r;
  246. }
  247.  
  248. void get_next_match()
  249. {
  250.     int n;
  251.  
  252.     remainder--;
  253.     if (++pos == DICSIZ * 2) {
  254. #ifdef CHECK_BREAK
  255.         check_break();
  256. #endif
  257.         (void) MOVE_LEFT((char *) &text[0], (char *) &text[DICSIZ], DICSIZ + MAXMATCH);
  258.         n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, lzh_infile);
  259.         remainder += n;  pos = DICSIZ;
  260. #ifdef SHOW_DOTS
  261.         (void) putc('.', stderr);
  262.         (void) fflush(stderr);
  263. #endif
  264.     }
  265.     delete_node();  insert_node();
  266. }
  267.  
  268. /* read from infile, compress, write to outfile */
  269. void encode(infile, outfile)
  270. FILE *infile;
  271. FILE *outfile;
  272. {
  273.     int lastmatchlen;
  274.     node lastmatchpos;
  275.  
  276.     /* make input/output files visible to other functions */
  277.     lzh_infile = infile;
  278.     lzh_outfile = outfile;
  279.  
  280.     allocate_memory();  init_slide();  huf_encode_start();
  281.     remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, lzh_infile);
  282. #ifdef SHOW_DOTS
  283.     (void) putc('.', stderr);
  284.     (void) fflush(stderr);
  285. #endif
  286.     matchlen = 0;
  287.     pos = DICSIZ;    insert_node();
  288.     if (matchlen > remainder) matchlen = remainder;
  289.     while (remainder > 0 && ! unpackable) {
  290.         lastmatchlen = matchlen;  lastmatchpos = matchpos;
  291.         get_next_match();
  292.         if (matchlen > remainder) matchlen = remainder;
  293.         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
  294. #if 0
  295.             d1log("%c", text[pos-1]);
  296. #endif
  297.             output(text[pos - 1], 0);
  298.         } else {
  299. #if 0
  300.         (void) putc('.', stderr); (void) fflush(stderr);
  301. #endif
  302.  
  303. #if 0
  304.             {
  305.                 int i;
  306.                 d1log("\nlastmatchlen=%d, pos=%d, lastmatchpos=%d",
  307.                             lastmatchlen, pos, lastmatchpos);
  308.                 d1log("\n[%d: ", (int) lastmatchlen);
  309.                 for (i = 0;  i < lastmatchlen;  i++)
  310.                     d1log("%c", text[lastmatchpos + i]);
  311.                 d1log("]\n");
  312.             }
  313. #endif
  314.  
  315.             output((uint) (lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD)),
  316.                     (uint) ((pos - lastmatchpos - 2) & (DICSIZ - 1)));
  317.             while (--lastmatchlen > 0) get_next_match();
  318.             if (matchlen > remainder) matchlen = remainder;
  319.         }
  320.     }
  321.     huf_encode_end();
  322. }
  323.  
  324. #ifdef NEED_MEMMOVE
  325. /* like memmove, but for moving stuff LEFT (downwards in memory) only!! */
  326. void move_left(dest, src, len)
  327. char *dest;
  328. char *src;
  329. int len;
  330. {
  331.     while (len-- > 0)
  332.         *dest++ = *src++;
  333. }
  334. #endif /* NEED_MEMMOVE */
  335.